# 40.组合总和II
# 给定一个候选人编号的集合candidates和一个目标数target ，找出candidates中所有可以使数字和为target的组合。
# candidates中的每个数字在每个组合中只能使用一次 。
# 注意：解集不能包含重复的组合。
#
# 示例1:
# 输入: candidates = [10, 1, 2, 7, 6, 1, 5], target = 8,
# 输出:
# [
#     [1, 1, 6],
#     [1, 2, 5],
#     [1, 7],
#     [2, 6]
# ]
#
# 示例2:
# 输入: candidates = [2, 5, 2, 1, 2], target = 5,
# 输出:
# [
#     [1, 2, 2],
#     [5]
# ]


class Solution:
    def combinationSum2(self, candidates: [int], target: int):
        candidates.sort()
        res = []
        path = []
        used = [0] * len(candidates)

        def backtracking(candidates, target, used, index):
            if sum(path) > target:
                return
            if sum(path) == target:
                res.append(path[:])
                return
            size = len(candidates)
            for i in range(index, size):
                if sum(path) + candidates[i] > target:
                    return
                if i > 0 and candidates[i] == candidates[i-1] and used[i-1] == 0:
                    continue
                path.append(candidates[i])
                used[i] = 1
                backtracking(candidates, target, used,i + 1)
                path.pop()
                used[i] = 0

        backtracking(candidates, target,used, 0)
        return res


if __name__ == '__main__':
    candidates = [10,1,2,7,6,1,5]
    target = 8
    # candidates = [10, 1, 2, 7, 6,1,5]
    # target = 8
    tmp = Solution()
    res = tmp.combinationSum2(candidates, target)
    print(res)